package Alibaba;

import java.util.PriorityQueue;
import java.util.Stack;

/**
 * @author zhangmin
 * @create 2022-01-17 13:51
 */
public class findKthLargest215 {
    /**
     * 215. 数组中的第K个最大元素
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * 1、小顶堆
     * 2、快速搜索
     * 3、排序后取k
     * */
    public int findKthLargest1(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            priorityQueue.offer(nums[i]);
            while (priorityQueue.size()>k){
                priorityQueue.poll();
            }
        }
        return priorityQueue.poll();
    }


    int partition(int[] nums,int left,int right){
        if (left==right) return left;
        int p=nums[left];
        int i=left,j=right+1;
        while (true){
            while (nums[++i]<p){
                if (i==right) break;
            }
            while (nums[--j]>p){
                if (j==left) break;
            }
            if (i>=j)break;
            swap(nums,i,j);
        }
        swap(nums,left,j);
        return j;
    }

    void swap(int[] nums,int x,int y){
        int temp=nums[x];
        nums[x]=nums[y];
        nums[y]=temp;
    }
    public int findKthLargest(int[] nums, int k) {
        int left=0,right=nums.length-1;
        k=nums.length-k;
        while (left<=right){
            int partition = partition(nums, left, right);
            if (partition<k){
                left=partition+1;
            }else if (partition>k){
                right=partition-1;
            }else {
                return nums[partition];
            }
        }
        return -1;
    }
}
